package offerbook;

/**
 * 统计一个数字在排序数组中出现的次数。
 * 比较优的算法肯定是O(logn)级别的。
 * 原题在leetcode34
 * @date 2020/3/11 14:55
 */
public class Code38_GetNumberOfKInSortArray {
    public static void main(String[] args) {
        int[]arr = {1,2,3,3,3,3,5,6};
        System.out.println(GetNumberOfK(arr, 4));

    }
    //方式1：遍历O(n)级别，略
    //方式2：二分查找
    public static int[] GetNumberOfK(int [] arr , int k) {
        if(arr == null || arr.length == 0) return new int[]{-1,-1};
        if(k < arr[0] || k > arr[arr.length-1]) return new int[]{-1,-1};
        return find(arr,k);
    }

    /**
     * 二分查找
     * @param arr
     * @param k
     * @return
     */
    private static int[] find(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;
        int mid = left + (right - left)/2;
        while (left <= right){
            if(arr[mid] > k){
                right = mid -1;
            }else if(arr[mid] < k) {
                left = mid + 1;
            }else {
                break;
            }
            mid = left + (right - left)/2;
        }
        //没找到
        if(left > right) return new int[]{-1,-1};
        //先找到对应target的index，然后分别去左边和右边查找
        int startIndex = findLeft(arr,k,mid);
        int endIndex = findRight(arr,k,mid);
        return new int[]{startIndex,endIndex};
    }
    //左侧查找，all the elements  <= k
    private static int findLeft(int[] arr, int k, int end) {
        // assert all the elements <= k and must has k
        int left = 0;
        int right = end;
        int mid = left + (right - left)/2;
        while (left <= right){
            if(arr[mid] == k){
                if(mid == 0) return 0;
                if(arr[mid] != arr[mid-1]) return mid;
                right = mid - 1;
            }else if(arr[mid] < k){
                left = mid + 1;
            }
            mid = left + (right - left)/2;
        }
        //never can reach here
        return -1;
    }
    private static int findRight(int[] arr, int k, int start) {
        //assert all the elements  >= k and must has k
        int left = start;
        int right = arr.length-1;
        int mid = left + (right - left)/2;
        while (left <= right){
            if(arr[mid] == k){
                if(mid == arr.length - 1) return arr.length - 1;
                if(arr[mid] != arr[mid + 1]) return mid;
                left = mid + 1;
            }else if(arr[mid] > k){
                right = mid - 1;
            }
            mid = left + (right - left)/2;
        }
        //never can reach here
        return -1;
    }


}
